 package editor.cn;

import java.util.Arrays;
class Solution1049 {
    public static void main(String[] args) {
        Solution solution = new Solution1049().new Solution();

    }

    class Solution {
        public int lastStoneWeightII(int[] stones) {
            //    题意就是01背包问题，从集合里面选择元素，问能够将容量为sum/2的背包最多装满多少即可！！

            // return dp1(stones);
            return dp2(stones);
        }

        private int dp2(int[] stones) {
            int n = stones.length;
            int sum = Arrays.stream(stones).sum();
            int[][] dp = new int[n][sum / 2 + 1];//dp[i][j]从0-i号里面选出石头，看能装满容量为j的背包最多为多少、
            for(int j=stones[0];j<=sum/2;j++){
                dp[0][j]=stones[0];
            }
            for (int i = 1; i < n; i++) {
                for (int j = 1; j <= sum / 2; j++) {
                    if (stones[i] <= j) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return sum - 2 * dp[n-1][sum / 2];
        }

        private int dp1(int[] stones) {
            int n = stones.length;
            int sum = Arrays.stream(stones).sum();
            int[] dp = new int[sum / 2 + 1];
            for (int i = 0; i < n; i++) {
                for (int j = sum / 2; j >= stones[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
            return sum - 2 * dp[sum / 2];
        }
//leetcode submit region end(Prohibit modification and deletion)
    }
}




















